#include <bits/stdc++.h>
using namespace std;
/**
 * logic: once matched, both left bracket and right bracket are no longer in consideration
 * first make sure every right bracket has a left bracket
 * then make sure every left left bracket has a right bracket
 * since * can be considered empty string, no need to consider left * any more.
*/
bool checkValidString(string s) {
    int n = s.length();
    stack<int> leftStack;
    stack<int> xinStack;
    for(int i = 0; i < n; ++i) {
        char c = s[i];
        if(c == '(') {
            leftStack.push(i);
        }else if(c == '*') {
            xinStack.push(i);
        }else {
            if(!leftStack.empty()) {
                leftStack.pop();
            }else if(!xinStack.empty()) {
                xinStack.pop();
            }else {
                return false;
            }
        }
    }
    while(!leftStack.empty()) {
        if(xinStack.empty()) return false;
        if(leftStack.top() < xinStack.top()){
            leftStack.pop();
            xinStack.pop();
        }else {
            return false;
        }
    }
    return true;
} 